package cn.springcloud.fix.demo.leecode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LengthOfLongestSubstring {

    public static void main(String[] args) {
        int len = lengthOfLongestSubstring3("abba");
        System.out.println(len);
    }

    // 一个字符串里最长不重复子串的长度
    public static int lengthOfLongestSubstring3(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, index = -1;//左指针
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dic.containsKey(c)) {//重复
                index = Math.max(index, dic.get(c)); // 更新左指针 i
            }
            dic.put(c, i); // 哈希表记录
            res = Math.max(res, i - index); // 更新结果
        }
        return res;
    }

    public static int lengthOfLongestSubstring4(String s) {
        int res = 0;
        List<Character> list = new ArrayList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (list.contains(c)) {
                int index = list.indexOf(c);
                res = Math.max(res, list.size());
                list = list.subList(index + 1, list.size());
            }
            list.add(c);
        }
        res = Math.max(res, list.size());
        return res;
    }

    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.equals("")) return 0;
        int max = 0;
        StringBuilder a = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            String c = String.valueOf(s.charAt(i));
            String s1 = a.toString();
            if (s1.contains(c)) {//有重复的了
                max = Math.max(max, s1.length());
                int index = s1.indexOf(c);
                s1 = s1.substring(index + 1);
                a = new StringBuilder(s1);
                a.append(c);
            } else {
                a.append(c);
            }
        }
        max = Math.max(max, a.toString().length());
        return max;
    }

    public static int lengthOfLongestSubstring2(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int val = dic.getOrDefault(c, -1);
            dic.put(c, i);
            tmp = tmp < i - val ? tmp + 1 : i - val; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}
